package com.cat.dataStructure;

import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-distance-in-arrays/
 * @create 2025/8/14 10:32
 * @since JDK17
 */

public class Solution05 {
    public int maxDistance(List<List<Integer>> arrays) {
        int n = arrays.size(), ans = Integer.MIN_VALUE;
        int[][] arr = new int[n][2];
        int[] premax = new int[n], rearmax = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i][0] = arrays.get(i).get(0);
            arr[i][1] = arrays.get(i).get(arrays.get(i).size() - 1);
        }
        // 求一个前缀最大值数组
        premax[0] = arr[0][1];
        rearmax[n - 1] = arr[n - 1][1];
        for (int i = 1; i < n; i++) {
            premax[i] = Math.max(premax[i - 1], arr[i][1]);
        }
        // 求一个后缀最大值数组
        for (int i = n - 2; i >= 0; i--) {
            rearmax[i] = Math.max(rearmax[i + 1], arr[i][1]);
        }
        ans = Math.max(rearmax[1] - arr[0][0], premax[n - 2] - arr[n - 1][0]);
        for (int i = 1; i < n - 1; i++) {
            ans = Math.max(ans, Math.max(premax[i - 1], rearmax[i + 1]) - arr[i][0]);
        }
        return ans;
    }

    public int maxDistance02(List<List<Integer>> arrays) {
        int mn = Integer.MAX_VALUE / 2;
        int mx = Integer.MIN_VALUE / 2;
        int ans = Integer.MIN_VALUE, x, y, n = arrays.size();
        for (List<Integer> array : arrays) {
            x = array.get(0);
            y = array.get(array.size() - 1);
            ans = Math.max(ans, Math.max(mx - x, y - mn));
            mn = Math.min(x, mn);
            mx = Math.max(y, mx);
        }
        return ans;
    }

}
